package algorithm_optimal_solution.TwoForkTree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//递归实现二叉树先序、中序、后序遍历
public class IteratorBeforeMidAfterTreeByRecursive {

    static class Node{
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    public void beforeTree(Node head,StringBuilder sb){
        if(head == null){
            return;
        }
        sb.append(head.getValue() + " ");
        beforeTree(head.getLeft(),sb);
        beforeTree(head.getRight(),sb);
    }

    public void midTree(Node head,StringBuilder sb){
        if(head == null){
            return;
        }
        midTree(head.getLeft(),sb);
        sb.append(head.getValue() + " ");
        midTree(head.getRight(),sb);
    }

    public void afterTree(Node head,StringBuilder sb){
        if(head == null){
            return;
        }
        afterTree(head.getLeft(),sb);
        afterTree(head.getRight(),sb);
        sb.append(head.getValue() + " ");
    }

    public void createTree(Node head,int[][] arr){
        int left = arr[head.getValue()][0];
        int right = arr[head.getValue()][1];
        if(left != 0){
            Node leftNode = new Node(left);
            head.setLeft(leftNode);
            createTree(leftNode,arr);
        }
        if(right != 0){
            Node rightNode = new Node(right);
            head.setRight(rightNode);
            createTree(rightNode,arr);
        }
    }

    public static void main(String[] args)throws IOException {
        IteratorBeforeMidAfterTreeByRecursive main = new IteratorBeforeMidAfterTreeByRecursive();
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String[] values = scanner.readLine().split(" ");
        int len = Integer.parseInt(values[0]);
        Node root = new Node(Integer.parseInt(values[1]));
        int[][] arr = new int[len + 1][2];
        String[] numbers = scanner.readLine().split(" ");
        arr[root.getValue()][0] = Integer.parseInt(numbers[1]);
        arr[root.getValue()][1] = Integer.parseInt(numbers[2]);
        for(int i = 1;i < len;i++){
            numbers = scanner.readLine().split(" ");
            int index = Integer.parseInt(numbers[0]);
            arr[index][0] = Integer.parseInt(numbers[1]);
            arr[index][1] = Integer.parseInt(numbers[2]);
        }
        StringBuilder sb = new StringBuilder();
        main.createTree(root,arr);
        main.beforeTree(root,sb);
        sb.append("\n");
        main.midTree(root,sb);
        sb.append("\n");
        main.afterTree(root,sb);
        System.out.print(sb);
    }
}
